package leetcode_300;

/**
 *@author 周杨
 *FindTheDuplicateNumber_287_ 给定一个数组n 里面全是1-n的数 找出重复的数
 *describe:不能破坏数组  用分治法或者找环起点的方法
 *2018年6月28日 下午5:22:56
 */
public class FindTheDuplicateNumber_287_ {

	public static void main(String[] args) {
		FindTheDuplicateNumber_287_ test=new FindTheDuplicateNumber_287_();
		System.out.println(test.findDuplicate(new int[] {1,3,4,2,2}));
		System.out.println(test.findDuplicate(new int[] {3,1,3,4,2}));
	}
	
	/**
	 * describe:二分搜索法 AC 20%
	 * 2018年6月28日 下午4:09:10
	 */
	public int findDuplicate(int[] nums) {
	    int l=1,r=nums.length-1;
	    while(l<=r) {
		    int m=(l+r)>>1;
		    int count=0;
		    for(int i=0;i<nums.length;++i) {
		    	if(nums[i]<=m)
		    		++count;
		    }
		    if(count<=m)//比m大的数太多 结果在右边
		    	l=m+1;
		    else
		    	r=m-1;
	    }
	    return l;
	}
	
	 /**
	 * describe:用找环的开头方法 AC 100%
	 * 2018年6月28日 下午5:22:33
	 */
	public int findDuplicate1(int[] nums) {
		    int n = nums.length;
		    int slow = n;
		    int fast = n;
		    do{
		        slow = nums[slow-1];
		        fast = nums[nums[fast-1]-1];
		    }while(slow != fast);
		    slow = n;
		    while(slow != fast){
		        slow = nums[slow-1];
		        fast = nums[fast-1];
		    }
		    return slow;
	 }
}
